package pers.vic.basics.datastructure.tree;

import pers.vic.basics.datastructure.linked.SingleLinkedList;

/**
 * @description:树接口(二叉树：左节点小于根节点小于右节点)
 * @author Vic.xu
 * @date: 2020/10/26 0026 14:54
 */
public interface TreeInterface {

    /**
     * 查找节点
     * @param key data
     * @return 节点
     */
    public BinaryNode find(Object key);

    /**
     * 插入节点
     * @param key data
     * @return  true | false
     */
    public boolean insert(Object key);

    /**
     * 删除节点
     * 1. 没有节点：找到父节点的引用置为null
     * 2. 只有一个节点：父节点的原引用指向其子节点
     * 3. 有两个子节点：找到前驱节点或者后继节点（删除）覆盖当前节点
     *    前驱：左子树的最右节点
     *    后继：右子树的最左节点
     * @param key data
     * @return true | false
     */
    public boolean delete(Object key);

    /**
     * 中序遍历：左→根→右
     */
    public void infixOrder();

    /**
     * 前序遍历：根→左→右
     */
    public void preOrder();

    /**
     * 后序遍历：左→右→根
     */
    public void postOrder();

    /**
     *  查找最大值
     * @return 节点
     */
    public BinaryNode max();

    /**
     * 查找最小值
     * @return 节点
     */
    public BinaryNode min();
}
